# -*- coding: utf-8 -*-
"""
 @Time    : 2021/1/25 上午11:50
 @Author  : tgy
 
"""
from Node import Node


def copyRandomList(head:Node) -> Node:
    ...
    if not head:
        return head

    # 拷贝链表
    node = head
    while node:
        ...
        tmp_node = node.next
        node.next = Node(node.val)
        node.next = tmp_node
        node = tmp_node


    # 设置random
    node = head
    while node:
        ...
        if node.random:
            node.next.random = node.random.next
        node = node.next.next

    # 分离新旧链表
    dummy_node = Node(0)
    tail_node = dummy_node

    node = head
    while node:
        tail_node.next = node.next
        tail_node = node.next
        node.next = tail_node.next
        node = node.next

    return dummy_node.next

if __name__ == '__main__':
    ...
